import java.util.Arrays;

/**
 * 冒泡优化思路
 * 1、如果子循环没交换了（其实已经有序了），跳出循环。
 * 2、记下最后一次交换的位置，后边没有交换，必然是有序的，然后下一次排序从第一个比较到上次记录的位置结束即可（1和2可以合并）。
 * 3、正反交替扫描，每一次把最大和最小都处理出来
 */
class BubbleSort {

    public static void main(String[] args) {
        int[] arr = new int[]{1, 5, 3, 4, 2, 6, 0};
        BubbleSort.sort3(arr, 7);
    }

    /**
     * 1和2的思路
     *
     * @param arr
     * @param len
     */
    void BubbleSort2(int arr[], int len) {
        int i = 0;
        int tmp = 0;
        int flag = 0;
        //用来记录最后一次交换的位置
        int pos = 0;
        int k = len - 1;
        for (i = 0; i < len - 1; i++) {//确定排序趟数
            pos = 0;
            int j = 0;
            flag = 0;
            for (j = 0; j < k; j++) {//确定比较次数
                if (arr[j] > arr[j + 1]) {
                    //交换
                    tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                    flag = 1;//加入标记
                    pos = j;//交换元素，记录最后一次交换的位置
                }
            }
            if (flag == 0) {//如果没有交换过元素，则已经有序
                return;
            }
            k = pos;//下一次比较到记录位置即可
        }
    }

    static void sort3(int arr[], int len) {
        int tmp = 0;
        boolean continueFlag = true;
        int end = len - 1;//记录上次最后的交换位置
        int endEx = 0;//用来记录正排最后一次交换的位置
        int headEx = 0;//用来记录倒排最后一次交换的位置

        for (int head = 0; head < len - 1 && continueFlag; head++) {//确定排序趟数
            continueFlag = false;
            for (int j = headEx; j < end; j++) {//正向扫描
                if (arr[j] > arr[j + 1]) {
                    //交换
                    tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                    continueFlag = true;//加入继续标记
                    endEx = j;//交换元素，记录最后一次交换的位置
                }
            }
            end = endEx;
            for (int j = endEx; j > head; j--) {//反向扫描
                if (arr[j] < arr[j - 1]) {
                    //交换
                    tmp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = tmp;
                    continueFlag = true;//加入继续标记
                    headEx = j;//交换元素，记录最后一次交换的位置
                }
            }
            head = headEx;
            if (continueFlag) {
                System.out.println("一次双向排序！");
            } else {
                System.out.println("排序完成！");
            }
        }
        System.out.println(Arrays.toString(arr));
    }


}